package main

import (
	"fmt"
	"math/rand"
	"os"
	"time"
)

/*
1、选择排序介绍
选择排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一个元素，经过和其他元素重整，再依原则交换位置后达到排序的目的
2、思想
选择排序也是一种简单的排序方法。它的基本思想是：
第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换
第三次从R[2]~R[n-1]中选取最小值，与R[2]交换，...，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换
第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排序的有序序列
*/
func SelectSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ { //i是交换次数
		max := arr[i]
		maxIndex := i
		//遍历后面1~len(arr)-1比较
		for j := i + 1; j < len(arr); j++ {
			if max < arr[j] { //找到真正的最大值
				max = arr[j]
				maxIndex = j
			}
		}
		//交换
		if maxIndex != i {
			arr[i], arr[maxIndex] = arr[maxIndex], arr[i]
		}
		fmt.Printf("第%d次%v\n", i+1, arr)
	}
}
func main() {
	var arr []int
	var num int
	var key string

	for {
		fmt.Println("1输入add构建数组")
		fmt.Println("2输入sort进行选择排序")
		fmt.Println("3输入exit退出")
		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("输入数组大小：")
			fmt.Scanln(&num)
			arr = make([]int, num)
			rand.Seed(time.Now().Unix())
			for i := 0; i < num; i++ {
				arr = append(arr, rand.Intn(100))
			}
			fmt.Println("构建完成：")
			fmt.Printf("%v", arr)
			fmt.Println()
		case "sort":
			SelectSort(arr)
		case "exit":
			os.Exit(0)
		}
	}

}
